//装满石头的背包的最大数量
/*现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。*/
class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks,
                    int additionalRocks) {
        priority_queue<int, vector<int>, greater<int>> p;
        int count = 0;
        for (int i = 0; i < capacity.size(); i++) {
            if (capacity[i] != rocks[i])
                p.push(capacity[i] - rocks[i]);
            else
                count++;
        }

        while (additionalRocks > 0 && p.size()) {
            if (additionalRocks >= p.top()) {
                additionalRocks -= p.top();
                p.pop();
                count++;
            } else {
                break;
            }
        }
        return count;
    }
};


//托普利茨矩阵
/*给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
*/
class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            int x = i;
            int y = x - i;
            int temp = matrix[x][y];
            while (x < m && y < n) {
                if (temp != matrix[x][y]) {
                    return false;
                }
                x++;
                y = x - i;
            }
        }
        for (int i = 1; i < n; i++) {
            int x = 0;
            int y = x + i;
            int temp = matrix[x][y];
            while (x < m && y < n) {
                if (temp != matrix[x][y]) {
                    return false;
                }
                x++;
                y = x + i;
            }
        }
        return true;
    }
};